class Graph:
    def __init__(self, arcs, verx):
        self.arcs = arcs
        self.verx = verx

    def bfs_traverse(self):
        self.visited = {}
        self.result = []
        for dot in self.verx:
            self.visited[dot] = False

        queue = []
        for dot in self.verx:
            print(self.visited)
            if not self.visited[dot]:
                queue.append(dot)
                print(queue)
                while len(queue) != 0:
                    q_dot = queue.pop(0)
                    self.visited[q_dot] = True
                    self.result.append(q_dot)
                    ajencent = self.first_ajencent_verx(q_dot)
                    print("dot is %s : first is %s " % (q_dot,ajencent))
                    print(queue)
                    while ajencent:
                        if (not self.visited[ajencent] and ajencent not in queue):
                            print(ajencent)
                            queue.append(ajencent)
                            print(queue)
                        ajencent = self.next_ajencent_verx(q_dot, ajencent)
        return self.result

    def dfs_traverse(self):
        self.visited = {}
        self.result = []
        for dot in self.verx:
            self.visited[dot] = False
        for dot in self.verx:
            if not self.visited[dot]:
                self.dfs(dot)
        return self.result

    def dfs(self, dot):
        self.visited[dot] = True
        # print(dot,end="-->")
        self.result.append(dot)
        ajencent = self.first_ajencent_verx(dot)
        while ajencent:
            if (not self.visited[ajencent]):
                self.dfs(ajencent)
            ajencent = self.next_ajencent_verx(dot, ajencent)

    def first_ajencent_verx(self, dot):
        index = self.index_of(dot)
        for i in range(len(self.verx)):
            if self.arcs[index][i] == 1:
                return self.dot_of(i)
        return None

    def next_ajencent_verx(self, dot, cur):
        index = self.index_of(dot)
        cur_index = self.index_of(cur)
        for i in range(cur_index + 1, len(self.verx)):
            if self.arcs[index][i] == 1:
                return self.dot_of(i)
        return None

    def index_of(self, dot):
        for index in range(len(self.verx)):
            if self.verx[index] == dot:
                return index

    def dot_of(self, index):
        return self.verx[index]


if __name__ == "__main__":
    arcs = [[0, 1, 1, 0, 0, 0, 0, 0],
            [1, 0, 0, 1, 1, 0, 0, 0],
            [1, 0, 0, 0, 0, 1, 1, 0],
            [0, 1, 0, 0, 0, 0, 0, 1],
            [0, 1, 0, 0, 0, 0, 0, 1],
            [0, 0, 1, 0, 0, 0, 1, 0],
            [0, 0, 1, 0, 0, 1, 0, 0],
            [0, 0, 0, 1, 1, 0, 0, 0]]
    verx = ['v1', 'v2', 'v3', 'v4', 'v5', 'v6', 'v7', 'v8']
    graph = Graph(arcs, verx)
    graph.dfs()
